package 剑指offer.链表;

import java.util.ArrayList;
import java.util.List;

/**
 *
 */
public class 第35题复杂链表的复制 {

    static class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    /*
    原始链表不只有一个next，在有多个指向的情况下复制该链表

    最原始的办法就是遍历两次链表 ，第一次复制只有 next 指向的，第二次复制有 random 指向的。但是显然复杂度较高 n^2

    分治法：分解问题求解每个子问题得到最终解

     */
    public static RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }

        RandomListNode currentNode = pHead;
        // 1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        // 这一步结束后pHead变成11223344，currentNode变成null
        while (currentNode != null) {
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            RandomListNode nextNode = currentNode.next;
            currentNode.next = cloneNode;
            cloneNode.next = nextNode;
            currentNode = nextNode;
        }

        currentNode = pHead;
        // 2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        while (currentNode != null) {
            currentNode.next.random = currentNode.random == null ? null : currentNode.random.next;
            currentNode = currentNode.next.next;
        }

        // 3、拆分链表，将链表拆分为原链表和复制后的链表
        // 此时 current = null
        currentNode = pHead;
        RandomListNode pCloneHead = pHead.next;
        while (currentNode != null) {
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            // 操作 currentNode
            cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
            currentNode = currentNode.next;
        }

        return pCloneHead;
    }

    public static void main2(String[] args) {
        RandomListNode a = new RandomListNode(1);
        RandomListNode b = new RandomListNode(2);
        RandomListNode c = new RandomListNode(3);
        RandomListNode d = new RandomListNode(4);
        a.next = b;
        b.next = c;
        c.next = d;

        a.random = c;
        d.random = b;
        c.random = a;

        RandomListNode ans = Clone(a);
        System.out.println(ans.label);
    }

    public static void methodTwo(List<Integer> a) {
        a = new ArrayList<>();// 就在这加了这一句
        a.add(101);
        System.out.println("main a=" + a.toString());
    }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>();
        a.add(100);
        methodTwo(a);
        System.out.println("main a=" + a.toString());
    }

}
